package LeetCode;

public class LC_440_KthSmallestinLexicographicalOrder {

    public static void main(String[] args) {

    }

    static class Solution {
        public int findKthNumber(int n, int k) {
            int res = 1;
            --k;
            while (k > 0) {
                long sum = getSum(res, n);
                if (sum <= k) {
                    k -= sum;
                    ++res;
                } else {
                    res *= 10;
                    --k;
                }
            }
            return res;
        }

        long getSum(long start, long n) {
            long end = start + 1;
            long sum = 0;
            while (start <= n) {
                sum += Math.max(0, (Math.min(n + 1, end) - start));
                start *= 10;
                end *= 10;
            }
            return sum;
        }

    }
}